import java.util.Arrays;

/**
 * 时间复杂度 : O(N^2)
 *     最好的情况是O(N) : 对于直接插入排序来说, 最好的情况就是数据有序的时候
 *     根据这个结论,推导出另一个结论 : 对于直接插入排序来说, 数据越有序,越快.
 * 空间复杂度 : O(1)
 * 稳定性 : 稳定的
 * 一个稳定的排序, 可以实现为不稳定的排序
 * 但是一个本身就不稳定的排序, 是不可以变成稳定的排序的
 */
public class TestSort {
    //插入排序
    public static void insertSort (int[] array) {
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] > temp) {
                    array[j+1] = array[j];
                } else {
                    //array[j+1] = temp;
                    break;
                }
            }
            //j回退到了 小于0的地方
            array[j+1] = temp;
        }
    }
    public static void main(String[] args) {
        int[] array = new int[]{10,9,8,7,6,52,1};
        insertSort(array);
        System.out.println(Arrays.toString(array));
    }
}
